package com.sfx.算法专题.链表.删除链表;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-01
 * Time: 23:19
 */
public class Code_3_removeNthFromEnd {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    static class Solution1 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if(head == null) return head;
            //1.根据快慢指针找到倒数第n个节点
            ListNode fast = head;
            ListNode slow = head;
            ListNode prev = null;
            while(fast != null && n>0) {
                fast = fast.next;
                n--;
            }
            while(fast != null) {
                fast = fast.next;
                prev = slow;
                slow = slow.next;
            }
            if(prev == null) {
                return head.next;
            }
            prev.next = slow.next;
            return head;
        }
    }
    static class Solution2 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode fast = dummyHead;
            ListNode slow = dummyHead;
            for(int i =0;i<=n;++i){
                fast = fast.next;
            }
            //两指针同时走
            while(fast!=null){
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return dummyHead.next;
        }
    }
}